package leetcode.数学;

/**
 * 有效的数独
 * <p>
 * 在一个 9*9 的数独格子上，输入一组解 char[][] board
 * 验证这个解是否有效
 *
 * 解法：遍历每一个格子，检查是否出现重复的数字
 * 遍历的时候肯定是一行一行的遍历，每一行里面再一列一列的遍历
 * 所以可以设置在遍历每一行数据的时候，保存每一行数字出现的情况
 * 保存每一列数字出现的情况
 * 保存每一个小格子里面数据出现的情况
 *
 */
public class Test36有效的数独 {


    /**
     * 统计数字出现的次数，若某一行里面同一个数字出现 2 次，返回 false
     *
     * @param board
     * @return
     */
    public static boolean isValidSudoku2(char[][] board) {
        // 这些二维数组表示的是第 N 行（列） Num 数字出现的次数
        int[][] rowCount = new int[10][9];
        int[][] columnCount = new int[10][9];
        int[][] subBoardCount = new int[10][9];
        // 遍历全部的格子
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 取出当前格子的数字
                int num = board[i][j] - '0';
                // 若这个数字在改行、或者该列、或者该小九宫格里面出现两次了，返回 false
                if (board[i][j] != '.' &&
                        (++rowCount[num][i] == 2  // 表示第 i 行数字 num 出现的次数
                                || ++columnCount[num][j] == 2  // 表示第 j 列数字 num 出现的次数
                                || ++subBoardCount[num][3 * (i / 3) + j / 3] == 2)  // 表示小九宫格 num 出现的次数
                ) {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isValidSudoku(char[][] board) {

        // 遍历每一个格子
        for (int i = 0; i < 9; i++) {
            // 记录每一行的数据出现的情况
            int[] row = new int[9];
            // 记录每一列的数字出现的情况
            int[] col = new int[9];
            // 记录数字在每一个以粗实线分隔的 3x3 宫内出现的情况
            int[] cube = new int[9];

            for (int j = 0; j < 9; j++) {
                // 其实只需要检查填入了数字的格子，放入 . 的格子直接不用管

                if (board[i][j] != '.') {
                    // 如果 row[index] 里面的数据是 1，表明这里已经被改写过了。
                    // 意思也就是说出现了重复的数字，不符合数独的要求，立刻返回 false
                    if (row[board[i][j] - '1'] == 1) {
                        return false;
                    } else {
                        row[board[i][j] - '1'] = 1;
                    }
                }

                if (board[j][i] != '.') {
                    if (col[board[j][i] - '1'] == 1) {
                        return false;
                    } else {
                        col[board[j][i] - '1'] = 1;
                    }
                }

                /**
                 * 观察行号规律：
                 * 第0个九宫格：000111222; 第1个九宫格：000111222; 第2个九宫格：000111222;
                 * 第3个九宫格：333444555; 第4个九宫格：333444555; 第5个九宫格：333444555;
                 * 第6个九宫格：666777888; 第7个九宫格：666777888; 第8个九宫格：666777888;
                 *
                 * 可见：
                 *  1. 对于每三个九宫格行号增3；
                 *  2. 对于单个九宫格，每三个格点行号增1。
                 *
                 * 因此，如何表示9个小九宫格（编号0~9），就可以通过以上规律得出：smallBoxIndex = (i/3)*3 + (j/3)
                 */
                int cubeX = 3 * (i / 3) + j / 3;  // 整数除法，不等同于数学除法，不能化简
                int cubeY = 3 * (i % 3) + j % 3;
                if (board[cubeX][cubeY] != '.') {
                    // 数字在每一个以粗实线分隔的 3x3 宫内只能出现一次
                    // 出现多次立刻返回
                    if (cube[board[cubeX][cubeY] - '1'] == 1) {
                        return false;
                    } else {
                        cube[board[cubeX][cubeY] - '1'] = 1;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        System.out.println(isValidSudoku2(board));
    }

}

